package com.xjh.basestudy.leetcode.question;

/**
 * @author XuJianHua
 * @version 1.0
 * @company 湖南安第斯信息科技有限公司, 版权所有
 * @date 2022/3/11 21:29
 */
/*
编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。
输入：strs = ["flower","flow","flight"]
输出："fl"

*/
public class Q14_LongestCommonPrefix {
    public static void main(String[] args) {
        String[] strs = new String[]{"flower", "flow", "flight"};
        System.out.println(prefix(strs));
    }

    // 解法一：纵向扫描
    private static String prefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        // 得到第一个字符串的长度
        int length = strs[0].length();
        //得到字符串的数量
        int count = strs.length;
        //按照第一个字符串的长度遍历
        for (int i = 0; i < length; i++) {
            //得到遍历顺序的字符
            char c = strs[0].charAt(i);
            //根据字符串的数量遍历（遍历第一个以后的字符串）
            for (int j = 1; j < count; j++) {
                //如果有字符串已经比较完了 或者 同一位置上字符不再相同 则证明不会有字符不再为同一前缀，结束遍历
                if (i == strs[j].length() || strs[j].charAt(i) != c) {
                    //截取并返回
                    return strs[0].substring(0, i);
                }
            }
        }
        //for 循环里面的有return被执行， 则外面的return不再执行，即调用一次则return一次
        return strs[0];
    }

    //解法二
    public static String longestCommonPrefix(String[] strs) {
        if (strs.length == 0)
            return "";
        String ans = strs[0];
        for (int i = 1; i < strs.length; i++) {
            int j = 0;
            for (; j < ans.length() && j < strs[i].length(); j++) {
                if (ans.charAt(j) != strs[i].charAt(j))
                    break;
            }
            ans = ans.substring(0, j);
            if (ans.equals(""))
                return ans;
        }
        return ans;
    }


}
/*
理解：外层for以第一个字符串为基准、内层for遍历剩下的字符串数量，如果不再匹配到相同的字符或者有字符串已经匹配完，则结束遍历
* */
/*
* 大概有这五种思路, 一般都会采用第四种, 但是耗时太多

1、所求的最长公共前缀子串一定是每个字符串的前缀子串。所以随便选择一个字符串作为标准，把它的前缀串，与其他所有字符串进行判断，看是否是它们所有人的前缀子串。这里的时间性能是O(m*n*m)。

2、列出所有的字符串的前缀子串，将它们合并后排序，找出其中个数为n且最长的子串。时间性能为O(n*m+m*n*log(m*n))

3、纵向扫描：从下标0开始，判断每一个字符串的下标0，判断是否全部相同。直到遇到不全部相同的下标。时间性能为O(n*m)。

4、横向扫描：前两个字符串找公共子串，将其结果和第三个字符串找公共子串……直到最后一个串。时间性能为O(n*m)。

5、借助trie字典树。将这些字符串存储到trie树中。那么trie树的第一个分叉口之前的单分支树的就是所求。
* */
